#include <bits/stdc++.h>
using namespace std;

/*
3477. 水果成篮 II
已解答
简单
相关标签
premium lock icon
相关企业
提示
给你两个长度为 n 的整数数组，fruits 和 baskets，其中 fruits[i] 表示第 i 种水果的 数量，baskets[j] 表示第 j 个篮子的 容量。

你需要对 fruits 数组从左到右按照以下规则放置水果：

每种水果必须放入第一个 容量大于等于 该水果数量的 最左侧可用篮子 中。
每个篮子只能装 一种 水果。
如果一种水果 无法放入 任何篮子，它将保持 未放置。
返回所有可能分配完成后，剩余未放置的水果种类的数量。

 

示例 1

输入： fruits = [4,2,5], baskets = [3,5,4]

输出： 1

解释：

fruits[0] = 4 放入 baskets[1] = 5。
fruits[1] = 2 放入 baskets[0] = 3。
fruits[2] = 5 无法放入 baskets[2] = 4。
由于有一种水果未放置，我们返回 1。

示例 2

输入： fruits = [3,6,1], baskets = [6,4,7]

输出： 0

解释：

fruits[0] = 3 放入 baskets[0] = 6。
fruits[1] = 6 无法放入 baskets[1] = 4（容量不足），但可以放入下一个可用的篮子 baskets[2] = 7。
fruits[2] = 1 放入 baskets[1] = 4。
由于所有水果都已成功放置，我们返回 0。

 

提示：

n == fruits.length == baskets.length
1 <= n <= 100
1 <= fruits[i], baskets[i] <= 1000
*/

// 法一
class Solution {
public:
    // 计算未放入篮子的水果数量
    int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) {
        int res = 0;
        // 遍历每一个水果
        for(int i = 0; i < fruits.size(); i++){
            // 遍历每一个篮子
            for(int j = 0; j < baskets.size(); j++){
                // 如果当前篮子的容量大于或等于当前水果的大小
                if(baskets[j] >= fruits[i]){
                    // 将该篮子的容量设为0，表示该篮子已被占用
                    baskets[j] = 0;
                    // 记录下成功放入一个水果
                    res++;
                    // 找到能放入当前水果的篮子后，无需再检查其他篮子，跳出内层循环
                    break;
                }
            }
        }
        // 总水果数减去成功放入篮子的水果数，得到未放入篮子的水果数量
        return fruits.size() - res;
    }
};

// 法二
class Solution {
public:
    int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) {
        // 每个篮子是否已经被使用
        vector<bool> used(baskets.size(), false);
        // 未放置的水果种类数量
        int unplaceCnt = 0;

        for (int fruit : fruits) {
            bool place = false;
            // 左-->右
            for (int j = 0; j < baskets.size(); j++) {
                if (!used[j] && baskets[j] >= fruit) {
                    // update flag
                    used[j] = true;
                    place = true;
                    break;
                }
            }
            if (!place)
                unplaceCnt++;
        }
        return unplaceCnt;
    }
};
